package com.feng.designpattern.strategy.sortarray;

/**
 * 
 * 快速排序是对冒泡排序的一种改进。它的基本思想是：
 * 通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据
 * 分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。复杂度O(nlng2(n))
 * 
 * @author Administrator
 * 
 */
public class QuickSort extends SortStrategy {
	public void sort(int[] data) {
		// 快速排序法(Quick Sort)
		long begin = System.currentTimeMillis();
		for (int k = 0; k < 1000000; k++) {
			quicksort(data, 0, data.length - 1);
		}
		long end = System.currentTimeMillis();
		System.out.println("快速法用时为：" + (end - begin));
		// 打印排序好的结果
		for (int i = 0; i < data.length; i++) {
			System.out.println(data[i]);
		}
	}

	/**
	 * 快速排序
	 * @param a 需要排序的列表
	 * @param low 起始位置
	 * @param high 结束位置
	 */
	private void quicksort(int a[], int low, int high) {
		int pivot;
		if (low < high) {
			pivot = partition(a, low, high);
			quicksort(a, low, pivot - 1);
			quicksort(a, pivot + 1, high);
		}
	}
	
	/**
	 * 选择中间数所在的位置(通常选取该数据段low--high的第一位:low)
	 * @param a 需要排序的列表
	 * @param low 起始位置
	 * @param high 结束位置
	 */
	private int partition(int a[], int low, int high) {
		int pivot, p_pos, i;
		p_pos = low;
		pivot = a[p_pos];
		for (i = low + 1; i <= high; i++) {
			if (a[i] > pivot) {
				p_pos++;
				swap(a, p_pos, i);
			}
		}
		swap(a, low, p_pos);
		return p_pos;
	}
	
	/**
	 * 交换i,j的位置
	 * @param a 需要排序的列表
	 * @param i 
	 * @param j 
	 */
	private void swap(int a[], int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
}
